package leetcode_ago.string_and_array;

/**
 * 给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。
 * 请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。
 * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
 * 为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2的长度为n
 */

import java.util.Arrays;

/**
 * 合并数组思路：
 * 1.nums2直接插入nums1后面，再排序，时间复杂度（m+n）log(m+n)
 * 2.双指针思想：依次取出两个数组头部，较小的放入一个新数组（创建了新空间：空间复杂度：m+n,时间复杂度:m+n）
 * 3.逆向双指针：nums1尾部空着nums2的长，依次从队尾取出较大值放到nums1尾部
 */
public class Num88_MergeArray {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {//3.
        //获取存在元素的尾部的索引，两者中较小值放在nums1尾部
       int m1=m-1;
        int n1=n-1;
        int tail=m+n-1;
        while (m1>=0||n1>=0){
            if(m1<0){
                nums1[tail--]=nums2[n1--];
            }else if(n1<0){
                nums1[tail--]=nums1[m1--];
            }else if(nums1[m1]<=nums2[n1]){
                nums1[tail--]=nums2[n1--];

            }else{
                nums1[tail--]=nums1[m1--];
            }
        }
        System.out.println(Arrays.toString(nums1));
    }

//    public static void merge(int[] nums1, int m, int[] nums2, int n) {//2(注意有一方走完的情况)
//        int index1=0,index2=0;//两个数组的首元素的索引
//        int[] str=new int[m+n];
//        int val=0;
//       while(index1<m||index2<n){
//           if(index1>=m){
//               val=nums2[index2++];
//           }else if(index2>=n){
//               val=nums1[index1++];
//           }else if(nums1[index1]<nums2[index2]){//此时1，2的值都还没有遍历完
//               val=nums1[index1++];
//           }else{
//               val=nums2[index2++];
//           }
//           str[index1+index2-1]=val;
//       }
//
//        for (int i=0;i<str.length;i++) {
//            nums1[i]=str[i];
//        }
//        System.out.println(Arrays.toString(nums1));
//    }

    public static void main(String[] args) {
        int[] nums1={1,2,3,0,0,0};
        int m=3;
        int[] nums2={2,5,6};
        int n=nums2.length;
        merge(nums1,m,nums2,n);
    }
//    public void merge(int[] nums1, int m, int[] nums2, int n) {//1
//        for (int i = 0; i != n; i++) {
//            nums1[m+i]=nums2[i];
//        }
//        Arrays.leetcode_ago.sort(nums1);
//    }
}
